package com.lintcode.solution;

import com.lintcode.solution.entity.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class EasySolution {
    
    public static void main(String[] agrs) {
        Arrays.asList("a", "b", "d").sort((e1, e2) -> {
            System.out.println(e1);
            System.out.println(e2);
            return e1.compareTo(e2);
        });
        System.out.println();
    }
    
    /**
     * Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees
     * are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if
     * two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will
     * be used as the node of new tree. Example 1:
     */
    public static TreeNode solution_617(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) {
            return null;
        }
        if (t1 == null) {
            t1 = new TreeNode(0);
        }
        if (t2 == null) {
            t2 = new TreeNode(0);
        }
        TreeNode result = new TreeNode(t1.val + t2.val);
        result.left = solution_617(t1.left, t2.left);
        result.right = solution_617(t1.right, t2.right);
        return result;
    }
    
    /**
     * Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a
     * circle, which means it moves back to the original place. The move sequence is represented by a string. And each
     * move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output
     * should be true or false representing whether the robot makes a circle. Example 1: Input: "UD" Output: true
     * Example 2: Input: "LL" Output: false
     */
    public static boolean solution_657(String moves) {
        int[] i = { 0, 0 };//(x,y)
        char[] arr = moves.toUpperCase().toCharArray();
        for (char c : arr) {
            switch (c) {
                case 'R':
                    i[ 0 ] += 1;
                    break;
                case 'L':
                    i[ 0 ] += - 1;
                    break;
                case 'U':
                    i[ 1 ] += 1;
                    break;
                case 'D':
                    i[ 1 ] += - 1;
                    break;
            }
        }
        return (i[ 0 ] == 0 && i[ 1 ] == 0);
    }
    
    /**
     * The Hamming distance between two integers is the number of positions at which the corresponding bits are
     * different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 231. Example: Input: x =
     * 1, y = 4 Output: 2 Explanation: 1   (0 0 0 1) 4   (0 1 0 0) The above arrows point to positions where the
     * corresponding bits are different.
     */
    public static int solution_461(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
    
    /**
     * Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order
     * of the elements in A. We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element
     * in A appears in B at index j. These lists A and B may contain duplicates. If there are multiple answers, output
     * any of them. For example, given A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28] We should return [1, 4, 3, 2,
     * 0] as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at
     * B[4], and so on.
     */
    public static int[] solution_760(int[] A, int[] B) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] C = new int[ A.length ];
        for (int i = 0; i < B.length; i++) {
            map.put(B[ i ], i);
        }
        
        for (int i = 0; i < A.length; i++) {
            C[ i ] = map.get(A[ i ]);
            System.out.println(map.get(A[ i ]));
        }
        return C;
    }
    
    public static List<Integer> solution_728(int left, int right) {
        List<Integer> list = new ArrayList<>();
        String str;
        for (int i = left; i <= right; i++) {
            str = String.valueOf(i);
            boolean flag = false;
            for (Character c : str.toCharArray()) {
                int a = Integer.valueOf(c.toString());
                if (a == 0 || i % a != 0) {
                    flag = true;
                    break;
                }
            }
            if (! flag) {
                list.add(i);
            }
        }
        return list;
    }
    
    /**
     * We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except
     * itself. Now, given an integer n, write a function that returns true when it is a perfect number and false when it
     * is not. Example: Input: 28 Output: True Explanation: 28 = 1 + 2 + 4 + 7 + 14
     */
    //时间太长
    public static boolean solution_507(int num) {
        int sum = 0;
        for (int i = 1; i <= num / 2; i++) {
            if (num % i == 0) {
                sum += i;
            }
        }
        return sum == num;
    }
    
    //正解
    public static boolean solution_507_(int num) {
        if (num == 0) {
            return false;
        }
        int a = num;
        while (a % 2 == 0) {
            a = a / 2;
        }
        for (int i = 2; i <= a; i++) {
            boolean flag = isPrimeNumbers(i);
            if (flag) {
                Double b = (Math.pow(2, i) - 1) * Math.pow(2, (i - 1));
                int c = b.intValue();
                if (c == num) {
                    return true;
                }
                if (c > num) {
                    return false;
                }
            }
        }
        return false;
    }
    
    public static boolean isPrimeNumbers(int a) {
        if (a == 1) {
            return false;
        }
        for (int i = 2; i <= (a % 2 == 0 ? a / 2 : ((a + 1) / 2)); i++) {
            if ((a % i == 0)) {
                return false;
            }
        }
        return true;
    }
    
    public static void solution_627() {
        //UPDATE salary SET sex = (CASE sex WHEN 'f' THEN 'm' ELSE 'f' END)
    }
    
    public static int solution_561(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += Math.min(nums[ i ], nums[ i + 1 ]);
        }
        return sum;
    }
    
    public static int solution_476(int num) {
        String str = Integer.toBinaryString(num);
        StringBuffer s = new StringBuffer();
        for (Character c : str.toCharArray()) {
            int a = Integer.valueOf(c.toString()) - 1;
            s.append(a >= 0 ? a : a * - 1);
        }
        return Integer.parseInt(s.toString(), 2);
    }
    
    public static String solution_344(String s) {
        StringBuffer str = new StringBuffer();
        char[] c = s.toCharArray();//hello
        for (int i = c.length - 1; i >= 0; i--) {
            str.append(c[ i ]);
        }
        return str.toString();
    }
    
    public static String solution_557(String s) {
        StringBuffer str = new StringBuffer();
        String[] strArr = s.split(" ");
        for (String s1 : strArr) {
            str.append(solution_344(s1)).append(" ");
        }
        return str.substring(0, str.length() - 1);
    }
    
    public static String[] solution_500(String[] words) {
        String str1 = "qwertyuiop";
        List<Character> list1 = new ArrayList<>();
        for (char c : str1.toCharArray()) {
            list1.add(c);
        }
        String str2 = "asdfghjkl";
        List<Character> list2 = new ArrayList<>();
        for (char c : str2.toCharArray()) {
            list2.add(c);
        }
        String str3 = "zxcvbnm";
        List<Character> list3 = new ArrayList<>();
        for (char c : str3.toCharArray()) {
            list3.add(c);
        }
        List<String> list = new ArrayList<>();
        for (String word1 : words) {
            String word = word1.toLowerCase();
            char c = word.charAt(0);
            boolean flag = true;
            if (list1.contains(c)) {
                for (char c1 : word.toCharArray()) {
                    if (! list1.contains(c1)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(word1);
                }
            }
            
            if (list2.contains(c)) {
                for (char c1 : word.toCharArray()) {
                    if (! list2.contains(c1)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(word1);
                }
            }
            
            if (list3.contains(c)) {
                for (char c1 : word.toCharArray()) {
                    if (! list3.contains(c1)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    list.add(word1);
                }
            }
        }
        String[] strArr = new String[ list.size() ];
        return list.toArray(strArr);
    }
    
    public static int solution_682(String[] ops) {
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        int a;
        for (String op : ops) {
            int index = list.size() - 1;
            if ("+".equals(op)) {
                //表示本轮得分是最后两个有效回合得分的总和。
                a = list.get(index) + list.get(index - 1);
            } else if ("C".equals(op)) {
                //表示你得到的最后一个有效回合的分数是无效的，应该被移除。
                a = - 1 * list.get(index);
                list.remove(index);
            } else if ("D".equals(op)) {
                //表示本轮得分是最后有效回合得分的两倍。
                a = list.get(index) * 2;
            } else {
                a = Integer.valueOf(op);
            }
            sum += a;
            if (! "C".equals(op)) {
                list.add(a);
            }
        }
        return sum;
    }
    
    public static List<String> solution_412(int n) {
        List<String> list = new ArrayList<>();
        Integer i = 1;
        String str;
        while (i <= n) {
            if (i % 3 == 0 && i % 5 == 0) {
                str = "FizzBuzz";
            } else if (i % 3 == 0) {
                str = "Fizz";
            } else if (i % 5 == 0) {
                str = "Buzz";
            } else {
                str = i.toString();
            }
            list.add(str);
            i++;
        }
        return list;
    }
    
    public static TreeNode solution_669(TreeNode root, int L, int R) {
        return trimBST(root, L, R);
    }
    
    public static TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null) {
            return null;
        }
        TreeNode node = null;
        TreeNode tLeft = null;
        TreeNode tRight = null;
        if (root.val >= L && root.val <= R) {
            //root符合条件
            node = new TreeNode(root.val);
        }
        tLeft = trimBST(root.left, L, R);
        tRight = trimBST(root.right, L, R);
        
        if (node != null) {
            node.left = tLeft;
            node.right = tRight;
            return node;
        } else if (tLeft != null) {
            return tLeft;
        } else if (tRight != null) {
            return tRight;
        }
        return null;
    }
    
    public static int solution_575(int[] candies) {
        Set<Integer> set = new HashSet<>();
        for (int candy : candies) {
            set.add(candy);
        }
        return set.size() >= candies.length / 2 ? candies.length / 2 : set.size();
    }
    
    public static int[][] solution_566(int[][] nums, int r, int c) {
        int a = nums.length;
        int b = nums[ 0 ].length;
        if (a * b != r * c) {
            return nums;
        } else {
            int[][] result = new int[ c ][ r ];
            LinkedList<Integer> list = new LinkedList<>();
            for (int[] num : nums) {
                for (int i : num) {
                    list.offer(i);
                }
            }
            int j = 0;
            for (int i = 0; i < result.length; i++) {
                for (int i1 = 0; i1 < result[ i ].length; i1++) {
                    result[ i ][ i1 ] = list.poll();
                }
            }
            return result;
        }
    }
    
    public static int solution_463(int[][] grid) {
        int sum = 0;
        int f = grid.length;
        int g = grid[ 0 ].length;
        for (int i = 0; i < f; i++) {
            for (int j = 0; j < g; j++) {
                if (grid[ i ][ j ] == 1) {
                    int a = i + 1;
                    int b = i - 1;
                    int c = j + 1;
                    int d = j - 1;
                    int e = 4;
                    e -= (a >= 0 && a < f) ? grid[ a ][ j ] : 0;
                    e -= (b >= 0 && b < f) ? grid[ b ][ j ] : 0;
                    e -= (c >= 0 && c < g) ? grid[ i ][ c ] : 0;
                    e -= (d >= 0 && d < g) ? grid[ i ][ d ] : 0;
                    sum += e;
                }
                
            }
        }
        return sum;
    }
    
    public static int[] solution_496(int[] nums1, int[] nums2) {
        int[] nums3 = new int[ nums1.length ];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            map.put(nums2[ i ], i);
        }
        for (int i = 0; i < nums1.length; i++) {
            int a = nums1[ i ];
            int index = map.get(a);
            for (int j = index; j < nums2.length; j++) {
                if (nums2[ j ] > a) {
                    nums3[ i ] = nums2[ j ];
                    break;
                } else {
                    nums3[ i ] = - 1;
                }
            }
        }
        return nums3;
    }
    
    public static List<Double> solution_637(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Map<Integer, Map<String, Double>> map = new HashMap<>();
        getSum(map, root, 0);
        int i = 0;
        while (map.get(i) != null) {
            Map<String, Double> m = map.get(i);
            double a = m.get("sum") / m.get("count");
            list.add(a);
            i++;
        }
        return list;
    }
    
    private static void getSum(Map<Integer, Map<String, Double>> map, TreeNode node, int deeply) {
        if (node == null) {
            return;
        }
        Map<String, Double> m = map.get(deeply);
        if (m == null) {
            m = new HashMap<>();
            m.put("sum", (double) node.val);
            m.put("count", 1.0);
            map.put(deeply, m);
        } else {
            m.put("sum", node.val + m.get("sum"));
            m.put("count", m.get("count") + 1);
        }
        
        getSum(map, node.left, deeply + 1);
        getSum(map, node.right, deeply + 1);
    }
    
    public static int solution_762(int L, int R) {
        int sum = 0;
        for (int i = L; i <= R; i++) {
            int oneCount = 0;
            for (char c : Integer.toBinaryString(i).toCharArray()) {
                if (c == '1') {
                    oneCount++;
                }
                
            }
            if (isPrimeNumbers(oneCount)) {
                sum++;
            }
        }
        return sum;
    }
    
    public static int solution_521(String a, String b) {
        if ("".equals(a) && "".equals(b)) {
            return - 1;
        } else if (("".equals(a) && ! "".equals(b)) || (! "".equals(a) && "".equals(b))) {
            return "".equals(a) ? b.length() : a.length();
        } else if (a.equals(b)) {
            return - 1;
        }
        if (a.length() >= b.length()) {
            int index = a.indexOf(b);
            if (index >= 0) {
                return solution_521(a.substring(0, index), b);
            } else {
                return a.length();
            }
        } else {
            int index = b.indexOf(a);
            if (index >= 0) {
                return solution_521(a, b.substring(0, index));
            } else {
                return b.length();
            }
        }
        
    }
    
    public static boolean solution_693(int n) {
        char[] chars = Integer.toBinaryString(n).toCharArray();
        for (int i = 1; i < chars.length; i++) {
            if (chars[ i ] == chars[ i - 1 ]) {
                return false;
            }
        }
        return true;
    }
    
    public static boolean canWinNim(int n) {
        if (n <= 3) {
            return true;
        }
        Set<Boolean> set = new HashSet<>();
        for (int i = 1; i <= 3; i++) {
            set.add(otherCanWinNim(n - i));
        }
        return set.size() == 1 && set.contains(true);
    }
    
    //肯定能赢
    public static boolean otherCanWinNim(int n) {
        if (n <= 3) {
            return false;
        } else {
            int s;
            boolean result = true;
            for (int i = 1; i <= 3; i++) {
                s = n - i;
                if (s <= 3) {
                    return false;
                } else {
                    result = canWinNim(s);
                }
            }
            return result;
        }
    }
    
    public static int solution_136(int[] nums) {
        if (nums.length == 1) {
            return nums[ 0 ];
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i += 2) {
            if (i + 1 >= nums.length) {
                return nums[ i ];
            }
            if (nums[ i ] != nums[ i + 1 ]) {
                return nums[ i ];
            }
        }
        return 0;
        
        //right solution
        /*int result = 0;
        for(int i : nums) {
            result ^= i;
        }
        return result;*/
    }
    
    public static int solution_485(int[] nums) {
        StringBuffer buffer = new StringBuffer(nums.length);
        for (int num : nums) {
            buffer.append(num);
        }
        int result = 0;
        for (String s : buffer.toString().split("0")) {
            result = Math.max(result, s.length());
        }
        return result;
    }
    
    public static boolean solution_766(int[][] matrix) {
        for (int i = 0; i < matrix.length - 1; i++) {
            for (int j = 0; j < matrix[ i ].length - 1; j++) {
                if (matrix[ i ][ j ] != matrix[ i + 1 ][ j + 1 ]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    public static int solution_104(TreeNode root) {
        Map<String, Integer> map = new HashMap<>();
        int deep = 0;
        map.put("maxDeep", deep);
        maxDeep(root, deep, map);
        return map.get("maxDeep");
    }
    
    private static void maxDeep(TreeNode root, int deep, Map<String, Integer> map) {
        if (root == null) {
            return;
        }
        int a = deep + 1;
        map.put("maxDeep", Math.max(a, map.get("maxDeep")));
        maxDeep(root.right, a, map);
        maxDeep(root.left, a, map);
    }
    
    public static TreeNode solution_226(TreeNode root) {
        if (root == null) {
            return null;
        }
        solution_226(root.left);
        solution_226(root.right);
        
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }
    
    public static int solution_695(int[][] grid) {
        int result = 0;
        return result;
    }
    
    
}


